#pragma once

#include <cmath>
#include <deque>
#include <string_view>
#include <string>
#include <vector>

namespace solution_068
{

class Solution
{
public:
    std::vector<std::string> fullJustify(const std::vector<std::string>& words, int maxWidth)
    {
        std::vector< std::deque< std::string_view > > lines;

        int linew = 0;
        for (auto& word : words) {
            if (!lines.empty() && linew + 1 + (int)word.size() <= maxWidth) {
                lines.back().emplace_back(word.data(), word.size());
                linew += 1 + word.size();
            } else {
                lines.emplace_back().emplace_back(word.data(), word.size());
                linew = word.size();
            }
        }

        std::vector<std::string> paragraph;

        for (int i = 0, linew = 0; i < (int)lines.size() - 1; ++i, linew = 0) {
            auto& line_words = lines.at(i);
            for (auto& word : line_words)
                linew += word.size();
            auto& line_str = paragraph.emplace_back();

            while (!line_words.empty()) {
                line_str += line_words.front();
                linew -= line_words.front().size();
                line_words.pop_front();
                int left_space = maxWidth - line_str.size() - linew;
                int space = (line_words.size() <= 1) ? left_space :
                    static_cast<int>(std::ceil(left_space * 1.0 / line_words.size()));
                line_str.resize(line_str.size() + space, ' ');
            }
        }

        auto& line_str = paragraph.emplace_back(lines.back().front());
        lines.back().pop_front();
        while (!lines.back().empty()) {
            line_str += " ";
            line_str += lines.back().front();
            lines.back().pop_front();
        }
        line_str.resize(maxWidth, ' ');

        return paragraph;
    }
};

}  /* namespace solution_068 */
